#include "MaxAscSeq.h"

#include <string.h>
#include <stdio.h>

/* 最长子序列 
 * 比如生成 100个数的随便数组, 按从大到小顺序的子序列的最大长度是多少?
 * 并打印这个最大长度的子序列
 */
int MaxAscSeqInArray(int * array, int arrayLen)
{
	int * LIS = new int[arrayLen];

	int MaxLIS = 1;
	int MaxLISIndex = 0;
	for(int i = 0; i < arrayLen; i++)
	{
		LIS[i] = 1;
		for(int j = 0; j < i; j++)
		{
			if(array[j] < array[i] && LIS[j] + 1 > LIS[i])
				LIS[i] = LIS[j] + 1;
		}

		if(LIS[i] > MaxLIS)
		{
			MaxLISIndex = i;
			MaxLIS = LIS[i];
		}
	}

	const int retRes = MaxLIS;

#if 1	
	int * resArray = new int[retRes];

	for(int i = MaxLISIndex; i >= 0 ; i--)
	{
		if(LIS[i] == MaxLIS) 
		{
			MaxLIS--;//only meet condition we need minus one.
			resArray[MaxLIS] =  array[i];
		}
	}

	//Normal sequnce output.
	for(int i = 0; i < retRes ; i++)
		std::cout << resArray[i] << "  ";

	delete resArray;
#endif


#if 0
	MaxLIS = 1;
	int preValue = array[0] -1;
	for(int i = 0; i <= MaxLISIndex ; i++)
	{
		if(LIS[i] == MaxLIS && array[i] > preValue)
		{
			preValue = array[i];
			std::cout << array[i] << "  ";
			MaxLIS++;
		}
	}
#endif



	delete[] LIS;

	return retRes;
}


/*
 * 请编写一个函数，输入两个字符串，求它们的最长公共子串，并打印出最长公共子串。
 *
 * 题目：如果字符串一的所有字符按其在字符串中的顺序出现在另外一个字符串二中，
 * 则字符串一称之为字符串二的子串。
 *
 * 注意，并不要求子串（字符串一）的字符必须连续出现在字符串二中。
 * 请编写一个函数，输入两个字符串，求它们的最长公共子串，并打印出最长公共子串。
 * 例如：输入两个字符串BDCABA和ABCBDAB，字符串BCBA和BDAB都是是它们的最长公共子串，
 * 则输出它们的长度4，并打印任意一个子串。
 */

int LongestCommonSubSequence(const char * src, const char * dest)
{
	return 0;
}


// Get the length of two strings' LCSs, and print one of the LCSs
// Input: pStr1         - the first string
//        pStr2         - the second string
// Output: the length of two strings' LCSs
int LCS(char* pStr1, char* pStr2)
{
      if(!pStr1 || !pStr2)
            return 0;

      size_t length1 = strlen(pStr1);
      size_t length2 = strlen(pStr2);
      if(!length1 || !length2)
            return 0;

      size_t i, j;

      // initiate the length matrix
      int **LCS_length;
      LCS_length = (int**)(new int[length1]);

      for(i = 0; i < length1; ++ i)
      {
            LCS_length[i] = (int*)new int[length2];
      }

      for(i = 0; i < length1; ++ i)
      {
            for(j = 0; j < length2; ++ j)
            {
                  LCS_length[i][j] = 0;
            }
      } 

      // initiate the direction matrix
      int **LCS_direction;
      LCS_direction = (int**)(new int[length1]);
      for( i = 0; i < length1; ++ i)
      {
            LCS_direction[i] = (int *)new int[length2];
      }

      for(i = 0; i < length1; ++ i)
      {
            for(j = 0; j < length2; ++ j)
            {
                  LCS_direction[i][j] = kInit;
            }
      }

      //Real content begin.
      for(i = 0; i < length1; ++ i)
      {
            for(j = 0; j < length2; ++ j)
            {
                  if(i == 0 || j == 0)//有一个子串的长度为1, 所以要么0 要么1.
                  {
                        if(pStr1[i] == pStr2[j])
                        {
                              LCS_length[i][j] = 1;
                              LCS_direction[i][j] = kLeftUp;
                        }
                        else
                        {
                              LCS_length[i][j] = 0;
                        }
                  }
                  else if(pStr1[i] == pStr2[j]) // a char of LCS is found, it comes from the left up entry in the direction matrix
                  {
                        LCS_length[i][j] = LCS_length[i - 1][j - 1] + 1;
                        LCS_direction[i][j] = kLeftUp;
                  }
                  else if(LCS_length[i - 1][j] > LCS_length[i][j - 1]) // it comes from the up entry in the direction matrix
                  {
                        LCS_length[i][j] = LCS_length[i - 1][j];
                        LCS_direction[i][j] = kUp;
                  }
                  else // it comes from the left entry in the direction matrix
                  {
                        LCS_length[i][j] = LCS_length[i][j - 1];
                        LCS_direction[i][j] = kLeft;
                  }
            }
      }

      LCS_Print(LCS_direction, pStr1, pStr2, length1 - 1, length2 - 1); //调用下面的LCS_Pring 打印出所求子串。

      return LCS_length[length1 - 1][length2 - 1];                      //返回长度。
}

 
// Print a LCS for two strings
// Input: LCS_direction - a 2d matrix which records the direction of 
//                        LCS generation
//        pStr1         - the first string
//        pStr2         - the second string
//        row           - the row index in the matrix LCS_direction
//        col           - the column index in the matrix LCS_direction
void LCS_Print(int **LCS_direction, char* pStr1, char* pStr2, size_t row, size_t col)
{
      if(pStr1 == NULL || pStr2 == NULL)
            return;
      size_t length1 = strlen(pStr1);
      size_t length2 = strlen(pStr2);
      if(length1 == 0 || length2 == 0 || !(row < length1 && col < length2))
            return;
      // kLeftUp implies a char in the LCS is found
      if(LCS_direction[row][col] == kLeftUp)
      {
            if(row > 0 && col > 0)
                  LCS_Print(LCS_direction, pStr1, pStr2, row - 1, col - 1);
            // print the char
            printf("%c", pStr1[row]);
      }
      else if(LCS_direction[row][col] == kLeft)
      {
            // move to the left entry in the direction matrix
            if(col > 0)
                  LCS_Print(LCS_direction, pStr1, pStr2, row, col - 1);
      }
      else if(LCS_direction[row][col] == kUp)
      {
            // move to the up entry in the direction matrix
            if(row > 0)
                  LCS_Print(LCS_direction, pStr1, pStr2, row - 1, col);
      }
}
